/**
 * Initialize your data structure here.
 */

 function Node(val){
    this.val=val;
    this.childs={};
}


var Trie = function() {
    this.root=new Node("");
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let node=this.root;
    for(let c of word){
        if(node.childs[c]===undefined){
            node.childs[c]=new Node(c);
        }
        node=node.childs[c];
    }
    node.end=true;
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node=this.root;
    for(let c of word){
        if(node.childs[c]==undefined){
            return false;
        }
        node=node.childs[c];
    }
    if(node.end){
        return true;
    }
    return false;
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let node=this.root;
    for(let c of prefix){
        if(node.childs[c]==undefined){
            return false;
        }
        node=node.childs[c];
    }
    return true;
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */



//  执行用时：
//  244 ms
//  , 在所有 JavaScript 提交中击败了
//  60.06%
//  的用户
//  内存消耗：
//  56 MB
//  , 在所有 JavaScript 提交中击败了
//  32.63%
//  的用户